package com.mlh.stack;

import com.mlh.greed.监控二叉树;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/6/24 14:47
 * @DESCRIPTION
 */
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。
// 输入：heights = [2,1,5,6,2,3]
// 输出：10
// 解释：最大的矩形为图中红色区域，面积为 10
public class 柱状图中最大的矩形 {
    // 思想：以每个柱子作为矩形的一部分，那这么该矩形的高度为该柱子，宽度就是左右两侧小于该柱子高度的下标位置的差值
    // 为什么可以这么做呢？因为最大的矩形一定会在某个柱子被占满的时候出现
    // 利用单调栈来找到每个柱子左边第一个小于自己的柱子，右边第一个小于自己的柱子
    // 找到之后 矩形的面积就是 （（右-1）-（左+1）+1）*该柱子高度
    public int method1(int[] heights) {
        int len = heights.length;
        int[] minFirstLeft = new int[len];//辅助数组记住左边第一个小
        int[] minFirstRight = new int[len];//辅助数组记住右边第一个小
        Arrays.fill(minFirstRight, -1);
        Arrays.fill(minFirstLeft, -1);
        Deque<Integer> stack = new LinkedList<>();//单调栈
        int maxSize = 0;
        //第一次填充minFirstRight
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                minFirstRight[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        stack.clear();
        //第二次填充minFirstLeft
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                minFirstLeft[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        //然后遍历所有柱子开始计算即可
        for (int i = 0; i < len; i++) {
            if (minFirstLeft[i] == -1 && minFirstRight[i] != -1) {
                maxSize = Math.max(heights[i] * ((minFirstRight[i] - 1) + 1), maxSize);
            } else if (minFirstLeft[i] != -1 && minFirstRight[i] == -1) {
                maxSize = Math.max(heights[i] * (len - 1 - (minFirstLeft[i] + 1) + 1), maxSize);
            } else if (minFirstLeft[i] == -1 && minFirstRight[i] == -1) {
                maxSize = Math.max(heights[i] * len, maxSize);
            } else {
                maxSize = Math.max(heights[i] * ((minFirstRight[i] - 1) - (minFirstLeft[i] + 1) + 1), maxSize);
            }
        }
        return maxSize;
    }

    public int practice(int[] heights) {
        int len = heights.length;
        int[] lowLeft = new int[len];
        int[] lowRight = new int[len];
        Arrays.fill(lowLeft, -1);
        Arrays.fill(lowRight, -1);
        LinkedList<Integer> stack = new LinkedList<>();
        int res=0;
        for (int i = 0; i <len; i++) {
            while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
                lowLeft[stack.pop()]=i;
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = len-1; i >=0 ; i--) {
            while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
                lowRight[stack.pop()]=i;
            }
            stack.push(i);
        }

        for (int i = 0; i < len; i++) {
            if(lowLeft[i]==-1&&lowRight[i]==-1){
                res=Math.max(res,heights[i]*len);
            }else if(lowLeft[i]!=-1&&lowRight[i]==-1){
                res=Math.max(res,(lowLeft[i]-1-(-1+1)+1)*heights[i]);
            }else if(lowLeft[i]==-1&&lowRight[i]!=-1){
                res=Math.max(res,(len-1-(lowRight[i]+1)+1)*heights[i]);
            }else{
                res=Math.max(res,(lowLeft[i]-1-(lowRight[i]+1)+1)*heights[i]);
            }
        }
        return res;
    }

    // 优化：栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
    // 因此实际上一次遍历就可以计算出最大面积，并且不需要辅助数组
    // 主要就是分析清楚如下三种情况：
    // 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
    //直接入栈即可，单调栈是从底到顶是不断增大的
    // 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
    // 这时候将栈顶元素出栈，然后该元素入栈，这样子可以避免相同高度且连在一起的元素去反复计算，没意义
    // 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
    //这时候就是 栈顶是cur 要入栈的是left 栈顶下一个元素是right 可以计算面积了
    // 里面要用while 将栈中所有大于要入栈元素的都出栈进行计算

    //practice2来完成这个优化
    public int practice2(int[] heights) {
        //为什么这里头尾都加了一个0
        //结尾加一个0，就会让栈里的所有元素，走到情况三的逻辑。
        //如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与8 进行比较，此时我们得到 mid（8），right（6），但是得不到 left。
        //因此头也要加一个0（不一定要是0，比0小也可以，我们主要是要这个索引位置0在遍历的过程中不会出栈），来充当left
        int[]newHeights=new int[heights.length+2];
        for (int i = 1; i <= heights.length; i++) {
            newHeights[i]=heights[i-1];
        }
        LinkedList<Integer>stack=new LinkedList<>();
        int res=0;
        for (int i = 0; i < newHeights.length; i++) {
            if(!stack.isEmpty()){
                if(newHeights[stack.peek()]<newHeights[i]){
                    stack.push(i);
                }else if(newHeights[stack.peek()]==newHeights[i]){
                    stack.pop();
                    stack.push(i);
                }else{
                    while(!stack.isEmpty()&&newHeights[stack.peek()]>newHeights[i]){
                        int cur=newHeights[stack.pop()],left=stack.peek(),right=i;
                        res=Math.max(res,(right-left-1)*cur);
                    }
                    stack.push(i);
                }
            }else{
                stack.push(i);
            }
        }
        return res;
    }
}
